-tape nondeterministic Turing machine

$ k-tape Turing machineの非決定性バージョン

定義

$ k \ge 2

$ M = (\Gamma, Q, \delta_0, \delta_1)

$ \Gamma：有限集合

$ \Box, \triangleright, 0, 1 \in \Gamma

$ Q：有限集合

$ q_\mathsf{start}, q_\mathsf{halt}, q_\mathsf{accept} \in Q

$ \delta_0, \delta_1\colon Q \times \Gamma^k \to Q \times \Gamma^{k-1} \times \{\mathsf{L, S,R}\}^k

nondeterministic choice$ \nu \in 2^*について各ステップ$ sにおいて$ k-tape Turing machineの$ \deltaの代わりに$ \delta_{\nu(s)}を用いた計算を行う

定義

入力$ xについて, nondeterministic choiceが存在し, 内部状態が$ q_\mathsf{accept}に到達するとき, $ M(x) = 1とかく

全てのnondeterministic choiceが$ q_\mathsf{halt}に到達し, $ q_\mathsf{accept}に到達するようなnondeterministic choiceが存在しないとき, $ M(x) = 0とかく

任意のnondeterministic choiceについて, 時間$ \le T(|x|)で内部状態が$ q_\mathsf{halt}か$ q_\mathsf{accept}に到達するとき$ Mは時間$ T(|x|)で停止するという